Varför bearbetar man en sorterad array snabbare än att bearbeta en osorterad array?

Du är ett offer för filialförutsägelse misslyckas.
Vad är grenprediktion?
Tänk på en järnvägskorsning:
Bild av Mecanismo, via Wikimedia Commons. Används under CC-By-SA 3.0-licensen.
Antag nu för argumentets skull att detta är tillbaka på 1800-talet - före långväga eller radiokommunikation.
Du är operatör för en korsning och du hör ett tåg komma. Du har ingen aning om vilken väg det ska gå. Du stannar tåget för att fråga föraren vilken riktning de vill ha. Och sedan ställer du in omkopplaren på rätt sätt.
Tågen är tunga och har mycket tröghet. Så de tar evigt att starta upp och sakta ner.
Finns det ett bättre sätt? Du antar vilken riktning tåget kommer att gå!
Om du gissade rätt fortsätter det.
Om du gissade fel stannar kaptenen, säkerhetskopierar och skriker på dig för att vända strömbrytaren. Då kan den starta om på den andra vägen.
Om du gissar rätt varje gång kommer tåget aldrig att behöva stanna. Om du gissar fel för ofta kommer tåget att spendera mycket tid på att stoppa, säkerhetskopiera och starta om.
Tänk på ett if-uttalande: På processornivå är det en greninstruktion:
Du är en processor och du ser en gren. Du har ingen aning om vilken väg det kommer att gå. Vad gör du? Du stoppar körningen och väntar tills de tidigare instruktionerna är klara. Fortsätt sedan längs rätt väg.
Moderna processorer är komplicerade och har långa rörledningar. Så de tar evigt att "värma upp" och "sakta ner".
Finns det ett bättre sätt? Du antar vilken riktning filialen kommer att gå!
Om du gissade rätt fortsätter du att köra.
Om du gissade fel måste du spola rörledningen och rulla tillbaka till filialen. Sedan kan du starta om den andra vägen.
Om du gissar rätt varje gång kommer utförandet aldrig att behöva stoppas. Om du gissar fel för ofta spenderar du mycket tid på att stoppa, rulla tillbaka och starta om.
Detta är gren förutsägelse. Jag erkänner att det inte är den bästa analogin eftersom tåget bara kan signalera riktningen med en flagga. Men på datorer vet inte processorn vilken riktning en gren kommer att gå förrän i sista stund.
Så hur skulle du strategiskt gissa för att minimera antalet gånger som tåget måste säkerhetskopiera och gå den andra vägen? Du tittar på tidigare historia! Om tåget går till vänster 99% av tiden, antar du vänster. Om det växlar, växlar du dina gissningar. Om det går en väg var tredje gång, antar du samma ...
Med andra ord försöker du identifiera ett mönster och följa det. Det är mer eller mindre hur grenprediktorer fungerar.
De flesta applikationer har välskötta grenar. Så moderna grenprediktorer uppnår vanligtvis> 90% träfffrekvenser. Men när vi står inför oförutsägbara grenar utan igenkännbara mönster är grenprediktorer praktiskt taget värdelösa.
Ytterligare läsning: "Branch prediktor" artikel på Wikipedia.
Som antyds ovan är den skyldige detta if-uttalande:
om (data [c]> = 128)
sum + = data [c];
Observera att data fördelas jämnt mellan 0 och 255. När data sorteras kommer ungefär första halvan av iterationerna inte att komma in i if-uttalandet. Efter det kommer de alla att ange if-uttalandet.
Detta är mycket vänligt för grenprediktorn eftersom filialen följer i flera riktningar i flera riktningar. Även en enkel mättningsräknare förutsäger grenen korrekt förutom de få iterationerna efter att den har bytt riktning.
Snabb visualisering:
T = gren tagit
N = gren tas inte
data [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
gren = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNTTTTTTTTT ... TTTTTTTTTT (lätt att förutsäga)
Men när data är helt slumpmässiga görs grenprediktorn värdelös, eftersom den inte kan förutsäga slumpmässiga data. Således kommer det troligen att finnas cirka 50% felberäkning (inte bättre än slumpmässig gissning).
data [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
gren = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (helt slumpmässigt - svårt att förutsäga)
Så vad kan man göra?
Om kompilatorn inte kan optimera filialen till ett villkorligt drag kan du prova några hack om du är villig att offra läsbarheten för prestanda.
Byta ut:
om (data [c]> = 128)
sum + = data [c];
med:
int t = (data [c] - 128) >> 31;
sum + = ~ t & data [c];
Detta eliminerar filialen och ersätter den med några bitvisa operationer.
(Observera att detta hack inte är exakt motsvarande det ursprungliga if-uttalandet. Men i det här fallet är det giltigt för alla inmatningsvärden för data [].)
Jämförelser: Core i7 920 @ 3,5 GHz
C ++ - Visual Studio 2010 - x64-utgåva
// Filial - Slumpmässig
sekunder = 11,777
// Gren - sorterad
sekunder = 2,352
// Grenfri - slumpmässig
sekunder = 2,564
// Grenfri - sorterad
sekunder = 2,587
Java - NetBeans 7.1.1 JDK 7 - x64
// Filial - Slumpmässig
sekunder = 10,93293813
// Gren - sorterad
sekunder = 5,643797077
// Grenfri -Slumpmässig
sekunder = 3.113581453
// Grenfri - sorterad
sekunder = 3,186068823
Observationer:
Med filialen: Det finns en enorm skillnad mellan sorterad och osorterad data.
Med hacket: Det finns ingen skillnad mellan sorterad och osorterad data.
I C ++ fallet är hacket faktiskt lite långsammare än med filialen när data sorteras.
En allmän tumregel är att undvika databaserad förgrening i kritiska slingor (som i det här exemplet).
Uppdatering:
GCC 4.6.1 med -O3 eller -ftree-vectorize på x64 kan generera ett villkorligt drag. Så det finns ingen skillnad mellan sorterad och osorterad data - båda är snabba.
(Eller något snabbt: för det redan sorterade fallet kan cmov vara långsammare, särskilt om GCC placerar den på den kritiska vägen istället för att bara lägga till, speciellt på Intel före Broadwell där cmov har 2-cykel latens: gcc-optimeringsflagga -O3 gör koden långsammare än -O2)
VC ++ 2010 kan inte generera villkorliga drag för denna gren även under / Ox.
Intel C ++ Compiler (ICC) 11 gör något mirakulöst. Det byter ut de två öglorna och hissar därmed den oförutsägbara grenen mot den yttre öglan. Så det är inte bara immunt mot felförutsägelser, det är också dubbelt så snabbt som vad VC ++ och GCC kan generera! Med andra ord utnyttjade ICC testslingan för att besegra riktmärket ...
Om du ger Intel-kompilatorn den grenlösa koden, vektoriserar den bara höger ... och är lika snabb som med grenen (med loop-utbytet).
Detta visar att även mogna moderna kompilatorer kan variera vilt i sin förmåga att optimera kod ...
|
Gren förutsägelse.
Med en sorterad matris är tillståndsdata [c]> = 128 först falsk för en rad värden och blir sedan sant för alla senare värden. Det är lätt att förutsäga. Med en osorterad matris betalar du förgreningskostnaden.
|
Anledningen till att prestanda förbättras drastiskt när data sorteras är att grenförutsägelsestraffet tas bort, vilket förklaras vackert i Mysticials svar.
Om vi ​​tittar på koden nu
om (data [c]> = 128)
sum + = data [c];
vi kan finna att betydelsen av denna speciella om ... annars ... gren är att lägga till något när ett villkor är uppfyllt. Denna typ av gren kan enkelt omvandlas till ett villkorligt draguttalande, som skulle sammanställas till en villkorlig flyttningsinstruktion: cmovl, i ett x86-system. Förgreningen och därmed den potentiella grenförutsägelsestraffet tas bort.
I C, alltså C ++, är uttalandet, som skulle kompileras direkt (utan någon optimering) i den villkorliga flyttningsinstruktionen i x86, den ternära operatören ...? ...: .... Så vi skriver om ovanstående uttalande till motsvarande:
sum + = data [c]> = 128? data [c]: 0;
Medan vi behåller läsbarheten kan vi kontrollera hastighetsfaktorn.
På en Intel Core i7-2600K @ 3,4 GHz och Visual Studio 2010 Release Mode är riktmärket (format kopierat från Mysticial):
x86
// Filial - Slumpmässig
sekunder = 8,885
// Gren - sorterad
sekunder = 1,528
// Grenfri - slumpmässig
sekunder = 3,716
// Grenfri - sorterad
sekunder = 3,71
x64
// Filial - Slumpmässig
sekunder = 11.302
// Gren - sorterad
sekunder = 1,830
// Grenfri - slumpmässig
sekunder = 2,736
// Grenfri - sorterad
sekunder = 2,737
Resultatet är robust i flera tester. Vi får stor fart när grenresultatet är oförutsägbart, men vi lider lite när det är förutsägbart. Faktum är att när du använder ett villkorligt drag är prestanda densamma oavsett datamönster.
Låt oss nu titta närmare genom att undersöka x86-enheten de genererar. För enkelhetens skull använder vi två funktioner max1 och max2.
max1 använder den villkorliga grenen om ... annars ...:
int max1 (int a, int b) {
om (a> b)
returnera a;
annan
retur b;
}
max2 använder den ternära operatören ...? ...: ...:
int max2 (int a, int b) {
returnera a> b? a: b;
}
På en x86-64-maskin genererar GCC -S enheten nedan.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
lämna
röta
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
lämna
röta
max2 använder mycket mindre kod på grund av instruktionen cmovge. Men den verkliga vinsten är att max2 inte innebär grenhopp, jmp, vilket skulle ha en betydande prestationsstraff om det förutspådda resultatet inte är rätt.
Så varför fungerar ett villkorligt drag bättre?
I en typisk x86-processor är utförandet av en instruktion uppdelad i flera steg. Ungefär har vi olika hårdvaror för att hantera olika steg. Så vi behöver inte vänta på att en instruktion är klar för att starta en ny. Detta kallas pipelining.
I ett grenfall bestäms följande instruktion av den föregående, så vi kan inte göra pipelining. Vi måste antingen vänta eller förutsäga.
I ett villkorligt flyttfall,den villkorliga flyttningsinstruktionen för körning är uppdelad i flera steg, men de tidigare stegen som Fetch och Decode beror inte på resultatet av den tidigare instruktionen; endast senare steg behöver resultatet. Således väntar vi en bråkdel av en instruktions exekveringstid. Det är därför som villkorsversionen är långsammare än grenen när förutsägelsen är enkel.
Boken Computer Systems: A Programmerers Perspective, andra upplagan förklarar detta i detalj. Du kan se avsnitt 3.6.6 för instruktioner för villkorlig flyttning, hela kapitel 4 för processorarkitektur och avsnitt 5.11.2 för särskild behandling för grenförutsägelser och felaktigt påföljder.
Ibland kan vissa moderna kompilatorer optimera vår kod för montering med bättre prestanda, ibland kan vissa kompilatorer inte (koden i fråga använder Visual Studios inbyggda kompilator). Att veta prestandaskillnaden mellan en gren och ett villkorligt drag när det är oförutsägbart kan hjälpa oss att skriva kod med bättre prestanda när scenariot blir så komplicerat att kompilatorn inte kan optimera dem automatiskt.
|
Om du är nyfiken på ännu fler optimeringar som kan göras med den här koden, överväg detta:
Börjar med den ursprungliga slingan:
för (osignerad i = 0; i <100000; ++ i)
{
för (osignerad j = 0; j  = 128)
sum + = data [j];
}
}
Med loop-utbyte kan vi säkert ändra denna loop till:
för (osignerad j = 0; j  = 128)
sum + = data [j];
}
}
Sedan kan du se att om villkorligt är konstant under hela körningen av i-slingan, så kan du lyfta ut om:
för (osignerad j = 0; j  = 128)
{
för (osignerad i = 0; i <100000; ++ i)
{
sum + = data [j];
}
}
}
Då ser du att den inre slingan kan kollapsas till ett enda uttryck, förutsatt att flytpunktsmodellen tillåter det (/ fp: snabbt kastas till exempel)
för (osignerad j = 0; j  = 128)
{
sum + = data [j] * 100000;
}
}
Den är 100 000 gånger snabbare än tidigare.
|
Utan tvekan skulle några av oss vara intresserade av sätt att identifiera kod som är problematisk för CPU: s grenprediktor. Valgrind-verktygets cachegrind har en gren-prediktorsimulator, aktiverad med flaggan --branch-sim = yes. Att köra det över exemplen i denna fråga, med antalet yttre slingor reducerat till 10000 och sammanställt med g ++, ger dessa resultat:
Sorterad:
== 32551 == Filialer: 656,645,130 (656,609,208 cond + 35,922 ind)
== 32551 == Felaktiga förutsägelser: 169.556 (169.095 cond + 461 ind)
== 32551 == Felaktigt värde: 0,0% (0,0% + 1,2%)
Osorterade:
== 32555 == Filialer: 655,996,082 (655,960,160 cond + 35,922 ind)
== 32555 == Felaktiga förutsägelser: 164 073 152 (164 072 692 cond + 460 ind)
== 32555 == Felaktig ränta: 25,0% (25,0% + 1,2%)
Borra ner i den rad-för-rad-utdata som produceras av cg_annotate ser vi för den aktuella slingan:
Sorterad:
Bc Bcm Bi Bim
10,001 4 0 0 för (osignerad i = 0; i <10000; ++ i)
. . . . {
. . . . // primär slinga
327,690,000 10,016 0 0 för (osignerad c = 0; c  = 128)
0 0 0 0 sum + = data [c];
. . . . }
. . . . }
Osorterade:
Bc Bcm Bi Bim
10,001 4 0 0 för (osignerad i = 0; i <10000; ++ i)
. . . . {
. . . . // primär slinga
327,690,000 10,038 0 0 för (osignerad c = 0; c  = 128)
0 0 0 0 sum + = data [c];
. . . . }
. . . . }
Detta gör att du enkelt kan identifiera den problematiska raden - i den osorterade versionen orsakar raden if (data [c]> = 128) 164,050,007 felberäknade villkorliga grenar (Bcm) under cachegrinds gren-prediktormodell, medan den bara orsakar 10,006 i den sorterade versionen .
Alternativt kan du på Linux använda subsystem för prestandaräknare för att utföra samma uppgift, men med inbyggd prestanda med CPU-räknare.
perf stat ./sumtest_sorted
Sorterad:
Statistik för prestationsräknare för './sumtest_sorted':
11808.095776 uppgiftsklocka # 0.998 CPU: er som används
1062 kontextomkopplare # 0,090 K / sek
14 CPU-migreringar # 0,001 K / sek
337 sidfel # 0,029 K / sek
26.487.882.764 cykler # 2.243 GHz
41 025 654 322 instruktioner # 1,55 inlägg per cykel
6.558.871.379 filialer # 555.455 M / sek
567 204 filial-missar # 0,01% av alla filialer
11.827228330 sekunder förfluten tid
Osorterade:
Prestandamotstatistik för './sumtest_unsorted':
28877.954344 uppgiftsklocka # 0.998 CPU: er som används
2584 kontextomkopplare # 0,089 K / sek
18 CPU-migreringar # 0,001 K / sek
335 sidfel # 0,012 K / sek
65.076.127.595 cykler # 2.253 GHz
41,032,528,741 instruktioner # 0,63 inlägg per cykel
6.560.579.013 filialer # 227.183 M / sek
1 646 394 749 filialmissar # 25,10% av alla filialer
28.935500947 sekunder förfluten tid
Det kan också göra annotering av källkod med demontering.
perf record -e gren-missar. / sumtest_unsorted
perfekt annotera -d sumtest_unsorted
Procent | Källkod och demontering av sumtest_unsorted
------------------------------------------------
...
: sum + = data [c];
0,00: 400a1a: mov -0x14 (% rbp),% eax
39.97: 400a1d: mov% eax,% eax
5.31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4,60: 400a26: cltq
0,00: 400a28: tillsätt% rax, -0x30 (% rbp)
...
Se prestandahandledningen för mer information.
|
Jag har just läst upp den här frågan och dess svar, och jag känner att ett svar saknas.
Ett vanligt sätt att eliminera grenförutsägelser som jag har funnit fungera särskilt bra på hanterade språk är en tabelluppslag istället för att använda en gren (även om jag inte har testat det i det här fallet).
Detta tillvägagångssätt fungerar generellt om:
det är ett litet bord och kommer troligen att cachas i processorn, och
du kör saker i en ganska snäv loop och / eller processorn kan förinstallera data.
Bakgrund och varför
Ur ett processorperspektiv är ditt minne långsamt. För att kompensera för skillnaden i hastighet är ett par cacher inbyggda i din processor (L1 / L2-cache). Så föreställ dig att du gör dina fina beräkningar och räkna ut att du behöver ett minne. Processorn kommer att få sin '' load '' -operation och laddar minnet i cachen - och använder sedan cachen för att göra resten av beräkningarna. Eftersom minnet är relativt långsamt kommer denna "belastning" att sakta ner ditt program.
Precis som grenförutsägelser optimerades detta i Pentium-processorerna: processorn förutspår att den måste ladda en bit data och försöker ladda den i cachen innan operationen faktiskt träffar cachen. Som vi redan har sett går grenförutsägelse ibland väldigt fel - i värsta fall måste du gå tillbaka och faktiskt vänta på en minnesbelastning, vilket kommer att ta för evigt (med andra ord: misslyckad grenförutsägelse är dålig, ett minne belastning efter att en gren förutsägelse misslyckas är bara hemskt!).
Lyckligtvis för oss, om minnesåtkomstmönstret är förutsägbart, kommer processorn att ladda det i sin snabba cache och allt är bra.
Det första vi behöver veta är vad som är litet? Medan mindre i allmänhet är bättre är en tumregel att hålla sig till uppslagstabeller som är <= 4096 byte i storlek. Som en övre gräns: om din uppslagstabell är större än 64 000 är det förmodligen värt att ompröva.
Konstruera ett bord
Så vi har kommit fram till att vi kan skapa ett litet bord. Nästa sak att göra är att få en uppslagsfunktion på plats. Uppslagsfunktioner är vanligtvis små funktioner som använder ett par grundläggande heltalsåtgärder (och, eller, eller, skift, lägg till, ta bort och kanske multiplicera). Du vill att dina inmatningar översätts av uppslagsfunktionen till någon form av "unik nyckel" i din tabell, som sedan helt enkelt ger dig svaret på allt arbete du ville att det skulle göra.
I det här fallet:> = 128 betyder att vi kan behålla värdet, <128 betyder att vi blir av med det. Det enklaste sättet att göra det är att använda ett 'OCH': om vi behåller det, OCH det med 7FFFFFFF; om vi vill bli av med det, OCH det med 0. Lägg också märke till att 128 är en kraft på 2 - så att vi kan fortsätta och göra en tabell med 32768/128 heltal och fylla den med en noll och mycket 7FFFFFFFF's.
Hanterade språk
Du kanske undrar varför detta fungerar bra på hanterade språk. När allt kommer omkring kontrollerar hanterade språk gränserna för matriserna med en gren för att se till att du inte förstör ...
Tja, inte exakt ... :-)
Det har gjorts en hel del arbete med att eliminera denna gren för hanterade språk. Till exempel:
för (int i = 0; i  = 128)? c: 0;
}
// Testa
DateTime startTime = System.DateTime.Now;
lång summa = 0;
för (int i = 0; i <100000; ++ i)
{
// Primär slinga
för (int j = 0; j  = 128. Det betyder att vi enkelt kan extrahera en enda bit som berättar om vi vill ha ett värde eller inte: genom att flytta data till höger 7 bitar, vi har en 0-bit eller en 1-bit, och vi vill bara lägga till värdet när vi har en 1-bit. Låt oss kalla den här biten "beslutsbit".
Genom att använda 0/1-värdet på beslutsbiten som ett index i en matris kan vi skapa kod som kommer att vara lika snabb oavsett om data sorteras eller inte sorteras. Vår kod kommer alltid att lägga till ett värde, men när beslutsbiten är 0 lägger vi till värdet någonstans vi inte bryr oss om. Här är koden:
// Testa
klocka_t start = klocka ();
lång lång a [] = {0, 0};
lång lång summa;
för (osignerad i = 0; i <100000; ++ i)
{
// Primär slinga
för (osignerad c = 0; c > 7);
a [j] + = data [c];
}
}
dubbel elapsedTime = static_cast  (klocka () - start) / CLOCKS_PER_SEC;
summa = a [1];
Den här koden slösar bort hälften av tilläggen men har aldrig ett fel i filialförutsägelsen. Det är oerhört snabbare på slumpmässiga data än versionen med ett faktiskt if-uttalande.
Men i mina tester var en tydlig uppslagstabell något snabbare än detta, förmodligen för att indexering till en uppslagstabell var något snabbare än bitförskjutning. Detta visar hur min kod ställer in och använder uppslagstabellen (fantasifullt kallad lut för "LookUp Table" i koden). Här är C ++ -koden:
// Deklarera och fyll sedan i uppslagstabellen
int lut [256];
för (osignerad c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Använd uppslagstabellen efter att den har byggts
för (osignerad i = 0; i <100000; ++ i)
{
// Primär slinga
för (osignerad c = 0; c  värde)
nod = nod-> pLeft;
annan
nod = nod-> pRight;
det här biblioteket skulle göra något liknande:
i = (x  värde);
nod = nod-> länk [i];
Här är en länk till den här koden: Red Black Trees, Eternally Confuzzled
|
I det sorterade fallet kan du göra bättre än att förlita dig på framgångsrik grenförutsägelse eller något grenlöst jämförelsetrick: ta bort grenen helt.
Arrayen är faktiskt partitionerad i en angränsande zon med data <128 och en annan med data> = 128. Så du borde hitta partitionspunkten med en dikotomisk sökning (med hjälp av Lg (arraySize) = 15 jämförelser), gör sedan en rak ackumulering från den punkten.
Något liknande (avmarkerat)
int i = 0, j, k = arraySize;
medan (i > 1;
if (data [j]> = 128)
k = j;
annan
i = j;
}
summa = 0;
för (; i > 1;
för (i = 0, k = arraySize; i  = 128? k: i) = j)
j = (i + k) >> 1;
för (sum = 0; i  = 128)
/ \
/ \
/ \
sant falskt
/ \
/ \
/ \
/ \
B) sum + = data [c]; C) för loop eller print ().
Utan gren förutsägelse skulle följande inträffa:
För att utföra instruktion B eller instruktion C måste processorn vänta tills instruktionen A inte når EX-steget i rörledningen, eftersom beslutet att gå till instruktion B eller instruktion C beror på resultatet av instruktion A. Så rörledningen kommer att se ut så här.
när om villkoret blir sant:
När om villkoret returnerar falskt:
Som ett resultat av att vänta på resultatet av instruktion A är de totala CPU-cyklerna i ovanstående fall (utan grenförutsägelse; för både sant och falskt) 7.
Så vad är gren förutsägelse?
Grenprediktorn kommer att försöka gissa vilken väg en gren (en if-then-else-struktur) kommer att gå innan detta är säkert känt. Det kommer inte att vänta på att instruktionen A ska nå EX-steget i rörledningen, men den kommer att gissa beslutet och gå till den instruktionen (B eller C i fallet med vårt exempel).
Vid en korrekt gissning ser rörledningen ungefär så här ut:
Om det senare upptäcks att gissningen var fel, kasseras de delvis utförda instruktionerna och rörledningen börjar om med rätt gren, vilket medför en fördröjning.
Tiden som slösas bort i fall av en felaktig förutsägelse av en gren är lika med antalet steg i rörledningen från hämtningssteget till exekveringssteget. Moderna mikroprocessorer tenderar att ha ganska långa rörledningar så att felförutsägelsefördröjningen är mellan 10 och 20 klockcykler. Ju längre rörledningen desto större är behovet av en bra grenprediktor.
I OP: s kod, den första gången när den villkorliga, har grenprediktorn ingen information för att basera förutsägelse, så första gången kommer den slumpmässigt att välja nästa instruktion. Senare i for-slingan kan den basera förutsägelsen på historien.
För en matris sorterad i stigande ordning finns det tre möjligheter:
Alla element är mindre än 128
Alla element är större än 128
Vissa startande nya element är mindre än 128 och senare blir de större än 128
Låt oss anta att prediktorn alltid kommer att anta den sanna grenen vid första körningen.
Så i det första fallet kommer det alltid att vara santgren eftersom historiskt sett alla dess förutsägelser är korrekta.
I det andra fallet kommer det initialt att förutsäga fel, men efter några iterationer kommer det att förutsäga korrekt.
I det tredje fallet kommer den initialt att förutsäga korrekt tills elementen är mindre än 128. Därefter kommer den att misslyckas under en tid och rätta sig själv när den ser grenförutsägelsefel i historien.
I alla dessa fall kommer felet att vara för mindre i antal och som ett resultat kommer det bara några gånger att behöva kasseras de delvis utförda instruktionerna och börja om med rätt gren, vilket resulterar i färre CPU-cykler.
Men i händelse av en slumpmässig osorterad matris måste förutsägelsen kasta de delvis utförda instruktionerna och börja om med rätt gren för det mesta och resultera i fler CPU-cykler jämfört med den sorterade matrisen.
|
Ett officiellt svar skulle vara från
Intel - Undvik kostnaden för felaktig förutsägelse i filialer
Intel - Branch and Loop Reorganization to Prevent Mispredictions
Vetenskapliga artiklar - grenförutsägelse datorarkitektur
Böcker: J.L. Hennessy, D.A. Patterson: Datorarkitektur: en kvantitativ strategi
Artiklar i vetenskapliga publikationer: T.Y. Yeh, Y.N. Patt gjorde många av dessa på grenförutsägelser.
Du kan också se från detta härliga diagram varför grenprediktorn blir förvirrad.
Varje element i den ursprungliga koden är ett slumpmässigt värde
data [c] = std :: rand ()% 256;
så prediktorn kommer att byta sida när std :: rand () blåser.
Å andra sidan, när den väl är sorterad, kommer prediktorn först att flytta till ett tillstånd som inte är starkt tagit och när värdena ändras till det höga värdet kommer prediktorn att genomgå tre förändringar hela vägen från starkt inte tas till starkt tas.
|
I samma rad (jag tror att detta inte lyfts fram av något svar) är det bra att nämna att du ibland (speciellt i programvara där prestandan spelar roll - som i Linux-kärnan) kan du hitta några om uttalanden som följande:
om (troligtvis (allt_is_ok))
{
/* Göra någonting */
}
eller liknande:
if (osannolikt (mycket_improbabelt_förhållande))
{
/* Göra någonting */
}
Både sannolikt () och osannolikt () är i själva verket makron som definieras genom att använda något som GCC: s __builtin_expect för att hjälpa kompilatorn att infoga förutsägelseskod för att gynna tillståndet med hänsyn till informationen från användaren. GCC stöder andra inbyggda program som kan ändra beteendet hos det körande programmet eller avge instruktioner på låg nivå som att rensa cacheminnet etc. Se den här dokumentationen som går igenom tillgängliga GCC: s inbyggda program.
Normalt finns denna typ av optimeringar huvudsakligen i applikationer i realtid eller inbäddade system där exekveringstiden är viktig och det är kritiskt. Om du till exempel letar efter något felvillkor som bara händer 1/10000000 gånger, varför inte informera kompilatorn om detta? På detta sätt antar grenförutsägelsen som standard att villkoret är falskt.
|
Ofta använda booleska operationer i C ++ producerar många grenar i det sammanställda programmet. Om dessa grenar är inuti öglor och är svåra att förutsäga kan de sakta ner körningen avsevärt. Booleska variabler lagras som 8-bitars heltal med värdet 0 för falskt och 1 för sant.
Booleska variabler är överbestämda i den meningen att alla operatörer som har booleska variabler som ingångskontroll om ingångarna har något annat värde än 0 eller 1, men operatörer som har booléer som utdata inte kan producera något annat värde än 0 eller 1. Detta gör operationer med Booleska variabler som input mindre effektiva än nödvändigt.
Tänk på exempel:
bool a, b, c, d;
c = a && b;
d = a || b;
Detta implementeras vanligtvis av kompilatorn på följande sätt:
bool a, b, c, d;
om (a! = 0) {
om (b! = 0) {
c = 1;
}
annat {
goto CFALSE;
}
}
annat {
KONTAKT:
c = 0;
}
om (a == 0) {
om (b == 0) {
d = 0;
}
annat {
goto DTRUE;
}
}
annat {
DTRUE:
d = 1;
}
Den här koden är långt ifrån optimal. Grenarna kan ta lång tid vid felförutsägelser. De booleska operationerna kan göras mycket effektivare om man vet med säkerhet att operanderna inte har några andra värden än 0 och 1. Anledningen till att kompilatorn inte gör ett sådant antagande är att variablerna kan ha andra värden om de inte är initialiserade eller kommer från okända källor. Ovanstående kod kan optimeras om a och b har initierats till giltiga värden eller om de kommer från operatörer som producerar booleska utdata. Den optimerade koden ser ut så här:
kol a = 0, b = 1, c, d;
c = a & b;
d = a | b;
char används istället för bool för att göra det möjligt att använda bitvisa operatorer (& och |) istället för de booleska operatorerna (&& och ||). De bitvisa operatörerna är enstaka instruktioner som bara tar en klockcykel. OR-operatören (|) fungerar även om a och b har andra värden än 0 eller 1. AND-operatören (&) och EXKLUSIV ELLER-operatören (^) kan ge inkonsekventa resultat om operanderna har andra värden än 0 och 1.
~ kan inte användas för INTE. Istället,du kan skapa en Boolean INTE på en variabel som är känd för att vara 0 eller 1 genom att XORera den med 1:
bool a, b;
b =! a;
kan optimeras för att:
kol a = 0, b;
b = a ^ 1;
a && b kan inte ersättas med a & b om b är ett uttryck som inte ska utvärderas om a är falskt (&& utvärderar inte b, & kommer). Likaså en || b kan inte ersättas med a | b om b är ett uttryck som inte ska utvärderas om a är sant.
Att använda bitvis operatörer är mer fördelaktigt om operanderna är variabler än om operanderna är jämförelser:
bool a; dubbel x, y, z;
a = x> y && z <5,0;
är optimalt i de flesta fall (såvida du inte förväntar dig att && uttrycket genererar många grenförutsägelser).
|
Det är säkert!...
Grenförutsägelse gör att logiken går långsammare på grund av bytet som sker i din kod! Det är som om du ska gå en rak gata eller en gata med många svängningar, för att den raka kommer att göras snabbare! ...
Om matrisen sorteras är ditt tillstånd felaktigt i det första steget: data [c]> = 128 blir sedan ett sant värde för hela vägen till slutet av gatan. Så kommer du snabbare till slutet av logiken. Å andra sidan, med en osorterad matris behöver du mycket vridning och bearbetning som gör att din kod går långsammare ...
Titta på bilden jag skapade åt dig nedan. Vilken gata kommer att avslutas snabbare?
Så programmatiskt orsakar grenförutsägelse att processen blir långsammare ...
Också i slutet är det bra att veta att vi har två typer av grenförutsägelser om att var och en kommer att påverka din kod annorlunda:
1. Statisk
2. Dynamisk
Förutsägelse av statisk gren används av mikroprocessorn första gången
en villkorlig gren påträffas och dynamisk gren förutsägelse är
används för efterföljande körningar av den villkorliga filialkoden.
För att effektivt kunna skriva din kod för att dra nytta av dessa
regler, när du skriver if-else eller byter uttalande, kontrollera mest
vanliga fall först och arbeta successivt ner till det minst vanliga.
Slingor kräver inte nödvändigtvis någon speciell beställning av kod för
statisk gren förutsägelse, som endast villkoret för loop iterator
används normalt.
|
Denna fråga har redan besvarats utmärkt många gånger. Fortfarande vill jag fästa gruppens uppmärksamhet på ännu en intressant analys.
Nyligen användes detta exempel (modifierat mycket lite) också som ett sätt att visa hur en kod kan profileras i själva programmet på Windows. Längs vägen visar författaren också hur man använder resultaten för att avgöra var koden spenderar mest av sin tid i både det sorterade och osorterade fallet. Slutligen visar stycket också hur man använder ett lite känt inslag i HAL (Hardware Abstraction Layer) för att bestämma hur mycket felförutsägelse som händer i det osorterade fallet.
Länken finns här:
En demonstration av självprofilering
|
Som det som redan har nämnts av andra, vad som ligger bakom mysteriet är Branch Predictor.
Jag försöker inte lägga till något utan förklarar konceptet på ett annat sätt.
Det finns en kort introduktion på wiki som innehåller text och diagram.
Jag gillar förklaringen nedan som använder ett diagram för att utarbeta Branch Predictor intuitivt.
I datorarkitektur är en grenprediktor en
digital krets som försöker gissa vilken väg en gren (t.ex. en
if-then-else-struktur) kommer att gå innan detta är säkert känt. De
Syftet med grenprediktorn är att förbättra flödet i
instruktionsrörledning. Grenprediktorer spelar en avgörande roll i
uppnå hög effektivitet i många moderna rörledningar
mikroprocessorarkitekturer som x86.
Tvåvägsförgrening implementeras vanligtvis med ett villkorligt hopp
instruktion. Ett villkorligt hopp kan antingen "inte tas" och fortsätta
körning med den första grenen av kod som följer omedelbart
efter det villkorliga hoppet, eller så kan det "tas" och hoppa till ett
annan plats i programminnet där den andra koden är
lagrade. Det är inte säkert känt om ett villkorligt hopp kommer att bli
tas eller inte tas förrän tillståndet har beräknats och
villkorligt hopp har passerat exekveringsstadiet i instruktionen
rörledning (se fig. 1).
Baserat på det beskrivna scenariot har jag skrivit en animeringsdemo för att visa hur instruktioner utförs i en pipeline i olika situationer.
Utan filialförutsägaren.
Utan grenförutsägelse måste processorn vänta tills
Villkorlig hoppinstruktion har passerat genomförandesteget före
nästa instruktion kan komma in i hämtningssteget i rörledningen.
Exemplet innehåller tre instruktioner och den första är en villkorlig hoppinstruktion. De två sistnämnda instruktionerna kan gå in i rörledningen tills den villkorliga hoppinstruktionen utförs.
Det tar 9 klockcykler för att tre instruktioner ska slutföras.
Använd Branch Predictor och ta inte ett villkorligt hopp. Låt oss anta att förutsägelsen inte tarvillkorligt hopp.
Det tar sju klockcykler för att tre instruktioner ska slutföras.
Använd Branch Predictor och ta ett villkorligt hopp. Låt oss anta att förutsägelsen inte tar det villkorliga hoppet.
Det tar 9 klockcykler för att tre instruktioner ska slutföras.
Tiden som slösas bort vid felaktig förutsägelse i en gren är lika med
antalet steg i rörledningen från hämtningssteget till
utför scenen. Moderna mikroprocessorer tenderar att ha ganska lång tid
pipelines så att felförutsägelsefördröjningen är mellan 10 och 20 klocka
cykler. Som ett resultat ökar behovet av en längre pipeline
mer avancerad grenprediktor.
Som du kan se verkar det som om vi inte har någon anledning att inte använda Branch Predictor.
Det är en ganska enkel demo som klargör den mycket grundläggande delen av Branch Predictor. Om dessa gifs är irriterande är du välkommen att ta bort dem från svaret och besökare kan också få live demo-källkoden från BranchPredictorDemo
|
Gren-förutsägelse vinst!
Det är viktigt att förstå att felförutsägelse i filialer inte saktar ner program. Kostnaden för en missad förutsägelse är precis som om grenförutsägelse inte fanns och du väntade på utvärderingen av uttrycket för att bestämma vilken kod som skulle köras (ytterligare förklaring i nästa stycke).
om (uttryck)
{
// Kör 1
} annat {
// Kör 2
}
När det finns ett if-else \ switch-uttalande måste uttrycket utvärderas för att bestämma vilket block som ska köras. I monteringskoden som genereras av kompilatorn infogas villkorliga greninstruktioner.
En greninstruktion kan få en dator att börja köra en annan instruktionssekvens och därmed avvika från dess standardbeteende för att utföra instruktioner i ordning (dvs. om uttrycket är falskt, hoppar programmet över koden för if-blocket) beroende på något tillstånd, vilket är uttrycket utvärdering i vårt fall.
Med detta sagt försöker kompilatorn att förutsäga resultatet innan det faktiskt utvärderas. Det kommer att hämta instruktioner från if-blocket, och om uttrycket visar sig vara sant, då underbart! Vi fick tiden det tog att utvärdera den och gjorde framsteg i koden; om inte så kör vi fel kod, rörledningen spolas och rätt block körs.
Visualisering:
Låt oss säga att du måste välja rutt 1 eller rutt 2. Väntar på att din partner ska kontrollera kartan, du har stannat vid ## och väntat, eller så kan du bara välja rutt1 och om du hade tur (rutt 1 är rätt rutt), då fantastiskt att du inte behövde vänta på att din partner skulle kontrollera kartan (du sparade den tid det skulle ha tagit honom att kontrollera kartan), annars kommer du bara att vända tillbaka.
Medan spolning av rörledningar är supersnabb är det idag värt att ta det här spelet. Att förutsäga sorterad data eller en data som förändras långsamt är alltid enklare och bättre än att förutsäga snabba förändringar.
O Väg 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
Väg 2 \ --------------------------------
|
På ARM behövs ingen gren, eftersom varje instruktion har ett 4-bitars tillståndsfält, som testar (till noll kostnad) något av 16 olika villkor som kan uppstå i processorstatusregistret, och om villkoret på en instruktion är falsk, instruktionen hoppas över. Detta eliminerar behovet av korta grenar, och det skulle inte finnas någon grenförutsägelse för denna algoritm. Därför skulle den sorterade versionen av denna algoritm gå långsammare än den osorterade versionen på ARM, på grund av extra kostnad för sortering.
Den inre slingan för denna algoritm skulle se ut ungefär som följande på ARM-monteringsspråket:
MOV R0, # 0 // R0 = summa = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, data // R2 = addr för dataarray (placera denna instruktion utanför yttre slinga)
.inner_loop // Etikett för inre slinga
LDRB R3, [R2, R1] // R3 = data [c]
CMP R3, # 128 // jämför R3 med 128
LÄGG TILL R0, R0, R3 // om R3> = 128, summera + = data [c] - ingen gren behövs!
LÄGG TILL R1, R1, # 1 // c ++
CMP R1, #arraySize // jämför c till arraySize
BLT inner_loop // Gren till inner_loop om c  ());
för (osignerad c = 0; c  = 128
summa = summa + data1 (j);
slutet
slutet
slutet
toc;
ExeTimeWithSorting = toc - tic;
Resultaten för ovanstående MATLAB-kod är som följer:
a: Förfluten tid (utan sortering) = 3479.880861 sekunder.
b: Förfluten tid (med sortering) = 2377.873098 sekunder.
Resultaten av C-koden som i @GManNickG får jag:
a: Förfluten tid (utan sortering) = 19,8761 sek.
b: Förfluten tid (med sortering) = 7.37778 sek.
Baserat på detta ser det ut som MATLAB är nästan 175 gånger långsammare än C-implementeringen utan sortering och 350 gånger långsammare med sortering. Med andra ord är effekten (av grenförutsägelse) 1,46x för MATLAB-implementering och 2,7x för C-implementeringen.
|
Antagandet från andra svar att man behöver sortera uppgifterna är inte korrekt.
Följande kod sorterar inte hela matrisen, utan bara segment av 200 element, och kör därmed snabbast.
Sortering av endast k-elementavsnitt slutför förbehandlingen i linjär tid, O (n), snarare än den O (n.log (n)) tid som behövs för att sortera hela matrisen.
# inkludera 
#include 
#include 
int main () {
int-data [32768]; const int l = storlek av data / storlek av data [0];
för (osignerad c = 0; c  = 128)
sum + = data [c];
}
}
std :: cout << static_cast  (klocka () - start) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum =" << sum << std :: endl;
}
Detta "bevisar" också att det inte har något att göra med något algoritmiskt problem som sorteringsordning, och det är verkligen grenförutsägelse.
|
Bjarne Stroustrups svar på denna fråga:
Det låter som en intervjufråga. Är det sant? Hur skulle du veta? Det är en dålig idé att svara på frågor om effektivitet utan att först göra några mätningar, så det är viktigt att veta hur man mäter.
Så jag försökte med en vektor på en miljon heltal och fick:
Redan sorterat 32995 millisekunder
Blandas 125944 millisekunder
Redan sorterat 18610 millisekunder
Blandas 133304 millisekunder
Redan sorterat 17942 millisekunder
Blandas 107858 millisekunder
Jag sprang det några gånger för att vara säker. Ja, fenomenet är verkligt. Min nyckelkod var:
ogiltig körning (vektor  & v, const sträng & etikett)
{
auto t0 = systemklocka :: nu ();
sortera (v.begin (), v.end ());
auto t1 = systemklocka :: nu ();
cout << etikett
<< duration_cast  (t1 - t0) .count ()
<< "millisekunder \ n";
}
ogiltig tst ()
{
vektor  v (1'000'000);
iota (v.begin (), v.end (), 0);
kör (v, "redan sorterad");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
kör (v, "blandad");
}
Åtminstone är fenomenet verkligt med denna kompilator, standardbibliotek och optimeringsinställningar. Olika implementeringar kan och ger olika svar. Faktum är att någon gjorde en mer systematisk studie (en snabb webbsökning hittar den) och de flesta implementeringar visar den effekten.
En anledning är grenförutsägelse: nyckeloperationen i sorteringsalgoritmen är "if (v [i]  = 128. Det betyder att vi enkelt kan extrahera en enda bit som berättar om vi vill ha ett värde eller inte: genom att flytta data till höger 7 bitar, vi har en 0-bit eller en 1-bit, och vi vill bara lägga till värdet när vi har en 1-bit. Låt oss kalla den här biten "beslutsbit".
Genom att använda 0/1-värdet på beslutsbiten som ett index i en matris kan vi skapa kod som kommer att vara lika snabb oavsett om data sorteras eller inte sorteras. Vår kod kommer alltid att lägga till ett värde, men när beslutsbiten är 0 lägger vi till värdet någonstans vi inte bryr oss om. Här är koden:
// Testa
klocka_t start = klocka ();
lång lång a [] = {0, 0};
lång lång summa;
för (osignerad i = 0; i <100000; ++ i)
{
// Primär slinga
för (osignerad c = 0; c > 7);
a [j] + = data [c];
}
}
dubbel elapsedTime = static_cast  (klocka () - start) / CLOCKS_PER_SEC;
summa = a [1];
Den här koden slösar bort hälften av tilläggen men har aldrig ett fel i filialförutsägelsen. Det är oerhört snabbare på slumpmässiga data än versionen med ett faktiskt if-uttalande.
Men i mina tester var en tydlig uppslagstabell något snabbare än detta, förmodligen för att indexering till en uppslagstabell var något snabbare än bitförskjutning. Detta visar hur min kod ställer in och använder uppslagstabellen (fantasifullt kallad lut för "LookUp Table" i koden). Här är C ++ -koden:
// Deklarera och fyll sedan i uppslagstabellen
int lut [256];
för (osignerad c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Använd uppslagstabellen efter att den har byggts
för (osignerad i = 0; i <100000; ++ i)
{
// Primär slinga
för (osignerad c = 0; c  värde)
nod = nod-> pLeft;
annan
nod = nod-> pRight;
det här biblioteket skulle göra något liknande:
i = (x  värde);
nod = nod-> länk [i];
Det är en bra lösning och kanske fungerar det.
|
Mycket aktiv fråga. Tjäna 10 rykte för att svara på den här frågan. Kravet på rykte hjälper till att skydda denna fråga från skräppost och icke-svar-aktivitet.
Inte svaret du letar efter? Bläddra bland andra frågor taggade java c ++ prestanda optimering gren-förutsägelse eller ställa din egen fråga.